package com.company;

import java.util.*;

public class BinaryTree extends Tree{
    private BinaryTree left;
    private BinaryTree right;
    private static List<Object> valueList = new ArrayList<>();
    private static boolean clean = true;
    public BinaryTree(Object value) {
        super(value);
    }

    public BinaryTree() {
    }

    public BinaryTree(Object value, List<Tree> children) {
        super(value, children);
    }

    public BinaryTree(Object value, BinaryTree left, BinaryTree right) {
        super(value);
        this.left = left;
        this.right = right;
    }


    public BinaryTree getLeft() {
        return left;
    }

    public void setLeft(BinaryTree left) {
        children.add(left);
        this.left = left;
    }

    public BinaryTree getRight() {
        return right;
    }

    public void setRight(BinaryTree right) {
        children.add(right);
        this.right = right;
    }

    public List<Object> preorderTraversal(){
        cleanValueList();
       return BinaryTree.preorderTraversal(this);
    }

    public List<Object> inorderTraversal(){
        cleanValueList();
        return inorderTraversal(this);
    }

    public List<Object> postorderTraversal(){
        cleanValueList();
        return postorderTraversal(this);
    }

    public List<Object> sequenceTraversal(){
        return sequenceTraversal(this);
    }

    public static List<Object> preorderTraversal(BinaryTree binaryTree){
        if (binaryTree==null){
            return valueList;
        }
        valueList.add(binaryTree.value);
        preorderTraversal(binaryTree.left);
        preorderTraversal(binaryTree.right);
        return valueList;
    }

    public static List<Object> inorderTraversal(BinaryTree binaryTree){
        if (binaryTree==null){
            return valueList;
        }

        inorderTraversal(binaryTree.left);
        valueList.add(binaryTree.value);
        inorderTraversal(binaryTree.right);
        return valueList;
    }



    public static List<Object> postorderTraversal(BinaryTree binaryTree){
        if (binaryTree==null){
            return valueList;
        }
        postorderTraversal(binaryTree.left);
        postorderTraversal(binaryTree.right);
        valueList.add(binaryTree.value);
        return valueList;
    }

    public static List<Object> sequenceTraversal(BinaryTree binaryTree){
        cleanValueList();
        if (binaryTree==null){
            return valueList;
        }
        Queue<BinaryTree> binaryTreeQueue = new LinkedList<>();
        binaryTreeQueue.add(binaryTree);
        while (!binaryTreeQueue.isEmpty()){
            BinaryTree node = binaryTreeQueue.poll();
            valueList.add(node.value);
            if (node.left!=null){
                binaryTreeQueue.offer(node.left);
            }
            if (node.right!=null){
                binaryTreeQueue.offer(node.right);
            }
        }
        return valueList;
    }

    public static void cleanValueList(){
        valueList.clear();
    }
    /**
     * 创建一颗二叉树
     * example:
     *         LinkedList<Object> inputList = new LinkedList<>
     *                 (Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null,
     *                         null, 8, null, 4}));
     *         BinaryTree binaryTree = BinaryTree.createBinaryTree(inputList);
     *         该用例返回了一颗二叉树
     *         3
     *        / \
     *       2   8
     *      / \   \
     *     9  10   4
     * @param inputList 二叉树的数据元素
     * @return 二叉树
     */
    public static BinaryTree createBinaryTree(LinkedList<Object>
                                               inputList) {
        BinaryTree node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;

        }
        Object data = inputList.removeFirst();
        if (data != null) {
            node = new BinaryTree(data);
            node.left = createBinaryTree(inputList);
            node.right = createBinaryTree(inputList);
        }
        return node;
    }

    public static void main(String[] args) {
        LinkedList<Object> inputList = new LinkedList<>
                (Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null,
                        null, 8, null, 4}));
        BinaryTree binaryTree = BinaryTree.createBinaryTree(inputList);
        assert binaryTree != null;
        List<Object> objects = binaryTree.preorderTraversal();
        System.out.println("///////////////////////////////////////////////////////");
        for (Object o:objects
             ) {
            System.out.println(o);
        }
        System.out.println("///////////////////////////////////////////////////////");
        objects = binaryTree.inorderTraversal();
        System.out.println("///////////////////////////////////////////////////////");
        for (Object o:objects
        ) {
            System.out.println(o);
        }
        System.out.println("///////////////////////////////////////////////////////");
        objects = binaryTree.postorderTraversal();
        System.out.println("///////////////////////////////////////////////////////");
        for (Object o:objects
        ) {
            System.out.println(o);
        }
        System.out.println("///////////////////////////////////////////////////////");
        objects = binaryTree.sequenceTraversal();
        System.out.println("///////////////////////////////////////////////////////");
        for (Object o:objects
        ) {
            System.out.println(o);
        }
    }
}
